class Solution {
public:
    void Postorder(vector<int>& v,TreeNode* root,stack<TreeNode*>& st)
    {
        if(root == nullptr)
            return;
        TreeNode* cur = root;
        TreeNode* prev;//记录上一个遍历的结点
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            //如果top的右子树为空或者已经遍历，则可以遍历该点
            TreeNode* top = st.top();
            if(top->right == nullptr || top->right == prev)
            {
                st.pop();
                v.push_back(top->val);
                prev = top;//prev记录该节点被遍历过
            }
            else
            {
                cur = top->right;//去栈顶结点的右子树遍历。
            }
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        if(root == nullptr)
            return v;
        Postorder(v,root,st);
        return v;
    }
};